package com.fh.twopointers;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 15. 三数之和
 * @author fuhao
 * @date 2025/10/14 22:10
 */
public class T15ThreeSum {
    class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            // 初始化返回的结果列表
            List<List<Integer>> result = new ArrayList<>();
            int n = nums.length;
            // 特判：如果数组为空或长度小于3，直接返回空结果
            if (nums == null || n < 3) {
                return result;
            }

            // 关键步骤1：对数组进行排序
            Arrays.sort(nums);

            // 遍历数组，固定第一个数 nums[i]
            for (int i = 0; i < n - 2; i++) {
                // 优化1：如果第一个数已经大于0，由于数组升序，后面不可能有三数之和为0的情况
                if (nums[i] > 0) {
                    break;
                }
                // 关键步骤2：对第一个数进行去重
                if (i > 0 && nums[i] == nums[i - 1]) {
                    continue;
                }

                // 初始化双指针
                int left = i + 1;
                int right = n - 1;

                // 双指针循环寻找
                while (left < right) {
                    int sum = nums[i] + nums[left] + nums[right];
                    if (sum == 0) {
                        // 找到一组解，添加到结果列表
                        result.add(Arrays.asList(nums[i], nums[left], nums[right]));

                        // 关键步骤3：找到解后，对左右指针进行去重
                        while (left < right && nums[left] == nums[left + 1]) {
                            left++;
                        }
                        while (left < right && nums[right] == nums[right - 1]) {
                            right--;
                        }
                        // 去重后，移动指针以进行下一次寻找
                        left++;
                        right--;
                    } else if (sum < 0) {
                        // 和太小，左指针右移以增大和
                        left++;
                    } else {
                        // 和太大，右指针左移以减小和
                        right--;
                    }
                }
            }
            return result;
        }
    }
}
